// 将两个降序链表合并为一个新的 降序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 


#include<bits/stdc++.h>
using namespace std;


  struct ListNode {
 	int val;
 	struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
  };
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param list1 ListNode类 
     * @param list2 ListNode类 
     * @return ListNode类
     */
    ListNode* MergeTwoLists(ListNode* list1, ListNode* list2) {
        // write code here
        if(list1==nullptr){
            return list2;
        }
        if(list2==nullptr){
            return list1;
        }
        ListNode* curr1=list1;
        ListNode* curr2=list2;
        ListNode* curr;
        if(curr1->val<curr2->val){
            curr=curr2;
            curr2=curr2->next;
        }
        else{
            curr=curr1;
            curr1=curr1->next;
        }
        ListNode* res=curr;
        while(curr1!=nullptr && curr2!=nullptr){
            if(curr1->val<curr2->val){
                curr->next=curr2;
                curr = curr->next;
                curr2=curr->next;
            }
            else{
                curr->next=curr1;
                curr=curr->next;
                curr1=curr1->next;
            }
        }
        if(curr1==nullptr){
            curr->next=curr2;
        }
        else{
            curr->next=curr1;
        }
        return res;
    }
};